package binary_tree.LeetCode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 后序遍历的迭代写法
 */
public class Num145 {
    public List<Integer> postorderTraversal(TreeNode root) {
         List<Integer> ret=new ArrayList<>();
         if(root==null){
             return ret;
         }
         TreeNode r1=root;
        Deque<TreeNode> stack=new ArrayDeque<>();
        //上一个完全处理完毕的节点
        TreeNode prev=null;
        while (r1!=null||!stack.isEmpty()){
            //先一路想左走到底
            while (r1!=null){
                stack.push(r1);
                r1=r1.left;
            }
            //此时注意栈顶元素
            r1=stack.poll();
            //检查右子树的情况
            if (r1.right==null||r1.right==prev){
                //此时右子树为空或者左子树已经被处理完毕，就可以访问r1
                ret.add(r1.val);
                //此时r1就是最新的处理完毕的节点
                prev=r1;
                //此时要让r1重新为空，才可以进行下一次循环
                r1=null;
            }else {
                //此时r1.right!null&&还没有被访问，就继续访问右子树
                stack.push(r1);
                //继续访问右子树
                r1=r1.right;
            }
        }
        return ret;
    }

}
